1. Field of the Invention
This invention relates to a digital data, multi-access computer communication system where a number of stations communicate with each other over a common frequency spectrum, by sharing a sequence of transmission time intervals.
2. Description of Prior Art
With the ever increasing penetration of digital communication into everyday business and personal lives, and a demand for an ever increasing accumulation of image and graphics oriented data communication services, like remote access to corporate computer resources, telecommuting, Internet access and Web surfing, remote and interactive education and entertainment, interactive video services, etc., service providers and network operators are striving to satisfy the demand.
The only way for the vast majority of residential customers to access data services is through voice-grade telephone modems. Currently, the fastest of modems perform at transmission speeds of at most 56 kilobits per second, however, commonly actual transmission speeds are much lower. Today's modems are capable of adequately supporting only narrow-band text-oriented services like e-mail and are inadequate in supporting applications requiring much higher speeds. These new applications can only be supported marginally, if at all, by today's voice-grade telephone modems.
A new breed of communication technologies was introduced to support the higher transmission speeds required by new broadband data services. This higher transmission speed could be in excess of 1 megabits per second. Telephone service providers, Cable TV (CaTV) service providers, wireless and cellular service providers, and even electric utility service providers are exploring and developing alternative, sometimes supplemental and sometimes competing, communication technologies and networking solution offerings for their customers to assist them in gaining access to the bandwidth-demanding new services.
The CaTV broadband data network provides two-way communication between subscriber computer systems and the CaTV head-end (H/E). From there, the two-way communications continue to the rest of the digital data network to which the CaTV plant is connected. Subscriber computer systems are connected to the CaTV H/E via a device called the cable modem, which can be located internally or externally with respect to the subscriber computer system. The cable modem connects to the H/E via the same CaTV cable used for regular analog TV viewing. FIG. 1 shows the typical topology of a two-way capable CaTV system. It consists of the CaTV H/E 101, and subscribers 104. The network topology is a tree-and-branch, which is an optimal topology for the distribution of a one way TV broadcast. The H/E 101 is located at the root of the tree while the subscribers 104 are located at the leaves of the tree. For increased signal quality, low maintenance, etc., the majority of the distance between the H/E 101 and the subscribers 104 is covered by fiber optic cables 106. A series of fiber nodes 102 are responsible for converting light signals to electromagnetic signals and vice-versa, for transmission over the coaxial cable region of the network 107. These dual medium CaTV plants are called hybrid fiber/coaxial (HFC).
Each fiber node 102 is at the root of a sub-tree that spans the subscribers in a logical neighborhood 105. A neighborhood 105 covers a few hundred subscribers 104. The coaxial cables that arrive at subscribers' homes carries signals in the frequency range of 5 MHz to about 750 MHz, or about 1 GHz in newer plants.
Data transmissions from cable modems to the H/E 101 typically occupy frequency bands in the range of 5 MHz to 42 MHz and are usually referred to as the upstream transmissions. Each such frequency band is also referred to as an upstream or return channel. Data transmissions from the H/E 101 to the cable modems typically occupy frequency bands in the region above 450 MHz and are usually referred to as the downstream transmissions. Each such frequency band is also referred to as a downstream channel.
During cable-modem power-on, the H/E 101 assigns to each cable-modem 104 a specific upstream channel, where they attempt all their message transmissions, and a specific downstream channel to receive all transmissions from the H/E 101. The message transmissions in both directions continue until H/E 101 decides otherwise. For ease of system management, cable-modems 104 that are assigned the same upstream channel are also assigned the same downstream channel.
To guarantee good signal quality and sufficient signal strength, bidirectional amplifiers 103 are added along the path from the CaTV 101 to subscribers 104. These amplifiers are bidirectional in the sense that operate over two distinct frequency regions, one that relates to upstream channels and one that relates to downstream channels.
While transmissions from the H/E 101 to stations, i.e., cable modems, on the downstream channel are under the exclusive control of the H/E 101, and thus well behaved and contention-free, coordinating transmissions from multiple stations to the H/E on an upstream channel is a more challenging task.
Unidirectional taps at each subscriber, disallow upstream transmission to be heard by other subscribers. Thus, on the one hand this increases the system security and privacy, on the other hand it guarantees that stations cannot communicate directly with each other, but they need to communicate through the H/E station via the help of an appropriate Medium Access Control (MAC) protocol, e.g., comprising a contention resolution component. Since, various stations cannot hear each other's upstream transmissions, during contention resolution, stations cannot listen for other transmissions prior to or during a message transmission of their own. As such, stations can coordinate their transmissions only under the explicit assistance from the H/E.
In order to communicate with the H/E, a cable modem needs to follow pre-established rules commonly referred to as a protocol suite. These rules regulate how the cable modem
a. may format the digital information into meaningful information messages, PA1 b. will transmit these messages on the cable plant, PA1 c. will share the communication resource, i.e., the cable, with other subscribers' modems, etc. PA1 1. transport, describing the way that information from or to a subscriber forms data messages, PA1 2. network, describing how messages travel and are routed through a communications network, PA1 3. medium access (MAC), describing how messages share common communication resources, PA1 4. physical, describing how a message is prepared for transmission on the communication medium, and etc. PA1 a. a contention/collision, resolution algorithm that is agreed upon and consistently executed by the cable modems, possibly facilitated by the H/E in order to resolve the message collisions; or PA1 b. allowing the H/E to explicitly or implicitly poll stations to transmit; or PA1 c. a combination of the a) and b).
A protocol suite comprises protocol layers like:
The network topology and architecture of a CaTV system, does not allow subscribers' cable modems tc listen to each other's transmissions. Thus, the possibility exists that two or more messages transmitted by different cable modems to overlap in time and frequency with each other resulting in destruction of the information that these messages carry. Message transmission, free from interference from other message transmissions, is achieved by incorporating in the MAC protocol:
Typically a data station is idle with nothing to transmit most of the time, thus polling stations for message transmissions could result in inefficient use of the communication resources, while active stations could experience a high delay until their turn comes to transmit. The low performance of a polling system, especially with low traffic loads, is exaggerated by the large round-trip propagation and message processing delays in a CaTV system, and the large number of subscribers attached to the CaTV system. More efficient CaTV system utilization is possible by permitting stations to transmit randomly and then utilize a contention resolution algorithm to cope with the possible message collisions.
Polling techniques work best at high traffic loads when most of the stations have something to transmit, while contention-based random access techniques work best at low to moderate traffic loads. Hence, hybrid solutions are most optimal for CaTV-based and other networks. In these networks, random access is used to register traffic load in a station to the H/E and then allow the H/E to poll only active stations on a contention-free basis, by reserving time intervals explicitly for given active stations. Message transmissions that result in collisions are referred to as contention-prone, while message transmissions that are guaranteed to be contention free are referred to as contention-free. Thus, in a network which operates with a hybrid MAC protocol, one can identify alternating contention-prone and contention-free operation phases during which contention-prone and contention-free message transmissions occur.
A good contention resolution algorithm results in an efficient use of network resources and in a fast resolution of possible collisions of simultaneously transmitted messages. Descriptions of contention resolution algorithms for multi-access computer communication can be found in the following references:
D. J. Aldous, "Ultimate instability of exponential back-off protocol for acknowledgment-based transmission control of random access communication channels," IEEE Trans. on Information Theory, vol. 33, no. 2, pp. 219-223, 1987; PA0 D. Bertsekas and D. Gallager, Data Networks, 2nd. ed., Prentice Hall, 1992; PA0 C. Bisdikian, "A review of random access algorithm," Int'l Workshop on Mobile Communications, pp. 123-127, Thessaloniki, Greece, September 1996; PA0 L. Georgiadis and P. Papantoni-Kazakos, "A collision resolution protocol for random access channels with energy detectors," IEEE Trans. on Communications, vol. 30, no. I 1, pp--2413-2420, November 1982; PA0 B. S. Tsybakov, "Survey of USSR Contributions to Random Multi-Access Communications," IEEE Trans. on Information Theory, vol. 31, no.2, pp. 143-165, March 1985; PA0 P. Mathys and P. Flajolet, "Q-ary collision resolution algorithms in random-access systems with free or blocked channel access," IEEE Trans. on Information Theory, vol. 31, no. 2, March 1985; PA0 L. Merakos and C. Bisdikian, "Delay analysis of the n-ary stack algorithm for a random access broadcast channel," IEEE Trans. on Inform. Theory, vol. 34, no. 5, September 1988; PA0 L. Georgiadis and P. Papantoni-Kazakos, "Limited Feedback Sensing Algorithms for the Packet Broadcast Channel," IEEE Trans. on Information Theory, vol. 31, no. 2, pp. 280-294, March 1985; and; PA0 W. Xu and G. Campbell, "A Distributed Queueing Random Access Protocol for a Broadcast Channel," Computer Communication Review, vol. 23, no. 4, pp. 270-278, October 1993.
Contention resolution is achieved by algorithms found in above references, by selecting appropriate retransmission time and by allowing the stations to retransmit repeatedly their collided messages at future times until these messages are successfully transmitted. The algorithms vary in the way that this retransmission time is selected. A station that has not yet successfully transmitted a message which has experienced a collision is called a "collided station", relative to this particular message. Similarly, the term "stations collide" describes stations that transmit messages that collide with each other.
According to a contention resolution algorithm's simplest form, a collided station, upon learning that its last message transmission resulted in a collision, randomly selects a waiting time interval and waits until this time interval expires before transmitting this message again. It is hoped that no other collided station selects a similar waiting time interval. The drawback of this simple algorithm is that even if two stations may not start transmitting at the same time, they may nevertheless still collide as long as one station starts transmitting while the other station still transmits.
Thus, to increase the efficiency of the algorithm, stations usually listen first and then wait for a transmission-free interval prior to their transmission. However, as previously mentioned, in a CaTV environment listening to other stations' transmissions is not feasible. Therefore, to decrease the possibility of collisions and thereby to increase the contention resolution efficiency, the transmission time axis is segmented into non-overlapping intervals large enough to accommodate a message transmission by a station. Stations are permitted to transmit only within the boundaries of these transmission intervals, thus messages can no longer partially overlap, they either overlap in their entirety or they do not overlap at all.
Two general classes of contention resolution algorithms are known in the literature. In the first class, usually referred to as the ALOHA class of algorithms, all collided stations following their collision, perform contention resolution against all active stations. This class of algorithms generally results in easier to implement algorithms, however, they are known to exhibit instabilities especially as the number of stations increases. For example, assuming a theoretically infinite number of stations, the number of stations waiting to transmit their message successfully increases without a bound independently of the traffic load. Advanced transmission control techniques are required in order to stabilize an algorithm within this class.
The second class of contention resolution algorithms is usually referred to as tree-search or stack algorithms because the contention resolution process can be graphically represented with the aid of a tree or a stack. In this class of algorithms, collided stations perform contention resolution only against the stations with which they have experienced a particular collision when all these stations transmitted in the same transmission interval. The contention resolution algorithms in this class generally result in relatively more complex, however inherently stable algorithms, and achieve substantially better efficiencies and delay characteristics than the algorithms of the first class. Hence, these algorithms are very attractive for data services that require low latency like real-time applications and/or high throughput like file data transfers.
Several tree and stack algorithms have been proposed in the open literature, referenced above. These algorithms pertain to the resolution of a contention that has occurred in a single transmission interval. Typically, in a tree-search algorithm, following a collision, the group of collided stations splits into a fixed number n of subgroups and contention resolution proceeds within each subgroup in sequence. L. Georgiadis and P. Papantoni-Kazakos, in "A collision resolution protocol for random access channels with energy detectors," IEEE Trans. on Communications, vol. 30, no. I 1, pp--2413-2420, November 1982., proposed a tree-search algorithm, a where stations that collide in a single transmission interval retransmit in the following transmission interval using a retransmission probability that depends on the number of stations collided during the first transmission interval.
W. Xu and G. Campbell, in "A Distributed Queueing Random Access Protocol for a Broadcast Channel," Computer Communication Review, vol. 23, no. 4, pp. 270-278, October 1993, proposed a tree-search algorithm for the resolution of collisions that occur over a fixed number m, m=2, 3, . . . , of successive transmission intervals, where the splitting parameter n is fixed and equal to m. The later situation attempts to take advantage of the long round-trip propagation delays in a CaTV network that may allow more than just a single transmission to be possible within a round-trip time. It should be noted that a station that transmits a message in a CaTV network needs to wait at least this round-trip time prior to it's next transmission, in order to learn the outcome of its original transmission.
Hybrid MAC solutions that combine both contention-prone and contention-free transmissions are preferred because of their good performance over all traffic loads. U.S. Pat. Nos. 4,736,371, 5,012,469 and 5,303,234 disclose hybrid MAC protocols using ALOHA-type contention resolution protocols that operate on a rigid, time-structured system that consists of a fixed size, successive time intervals, grouped into fixed size time frames. U.S. Pat. Nos. 4,745,599 and 4,774,707 describe hybrid MAC systems also using ALOHA-type contention resolution protocols. However, in these systems, contention-based transmissions can occur in asynchronous fashion in that, during asynchronous operating phases, transmissions from various stations start at random times. This simplifies the operation of a station but, at a cost of lower network efficiency due to wasted bandwidth from partially overlapped message transmissions.
Regarding hybrid MAC protocols that use tree-search based contention resolution protocols, U.S. Pat. Nos. 5,390,181 and 5,590,131 propose hybrid MAC protocols with a rigid time-structure that consists of a repeated pattern comprised a fixed number N of fixed size successive transmission time intervals for contention-prone transmissions followed by a single fixed size transmission time interval for contention-free transmissions. The later U.S. Pat. No. 5,590,131 is based on the first one U.S. Pat. No. 5,390,181 and on the related reference, W. Xu and G. Campbell, "A Distributed Queueing Random Access Protocol for a Broadcast Channel," Computer Communication Review, vol. 23, no. 4, pp. 270-278, October 1993, where extra algorithmic rules are added to reduce the number N needed to achieve a given performance level compared to the former patent. The marginal improvement in performance though may not support the added complexity due to the additional algorithmic rules.
What would be very beneficial is a way to further increase the MAC protocol efficiency and to increase the flexibility of the system operator to dynamically assign time intervals for contention-prone and contention-free transmissions.